﻿using System;
using System.Collections.Generic;
using System.Linq;

// 定义节点类
public class GraphNode
{
    public int Id { get; set; }
    public double Distance { get; set; }
    public bool Visited { get; set; }
}

// 定义边类
public class Edge
{
    public GraphNode From { get; set; }
    public GraphNode To { get; set; }
    public double Weight { get; set; }
}

// Dijkstra算法类
public class DijkstraAlgorithm
{
    public void FindShortestPath(List<Edge> edges, List<GraphNode> nodes, int sourceNodeId)
    {
        // 初始化起点距离为0，其他节点距离为无穷大
        foreach (var node in nodes)
        {
            node.Distance = double.PositiveInfinity;
        }
        nodes[sourceNodeId - 1].Distance = 0;

        // 访问所有节点
        for (int i = 0; i < nodes.Count; i++)
        {
            // 寻找当前最小距离的未访问节点
            var current = nodes.FirstOrDefault(n => !n.Visited);
            if (current == null) break;

            // 将当前节点标记为已访问
            current.Visited = true;

            // 遍历当前节点的所有邻接节点
            foreach (var edge in edges.Where(e => e.From.Id == current.Id))
            {
                var neighbor = edge.To;
                var alt = current.Distance + edge.Weight;
                if (alt < neighbor.Distance)
                {
                    neighbor.Distance = alt;
                }
            }
        }
    }
}

// 测试类
public class Program
{
    static void Main()
    {
        // 创建节点
        var nodes = new List<GraphNode>
        {
            new GraphNode { Id = 1 },
            new GraphNode { Id = 2 },
            new GraphNode { Id = 3 },
            new GraphNode { Id = 4 },
            new GraphNode { Id = 5 },
            new GraphNode { Id = 6 }
        };

        // 创建边
        var edges = new List<Edge>
        {
            new Edge { From = nodes[0], To = nodes[1], Weight = 250 },
            new Edge { From = nodes[0], To = nodes[2], Weight = 400 },
            new Edge { From = nodes[1], To = nodes[2], Weight = 100 },
            new Edge { From = nodes[1], To = nodes[3], Weight = 300 },
            new Edge { From = nodes[2], To = nodes[3], Weight = 150 },
            new Edge { From = nodes[2], To = nodes[4], Weight = 275 },
            new Edge { From = nodes[3], To = nodes[4], Weight = 100 },
            new Edge { From = nodes[3], To = nodes[5], Weight = 200 },
            new Edge { From = nodes[4], To = nodes[5], Weight = 150 }
        };

        // 实例化Dijkstra算法对象
        var dijkstra = new DijkstraAlgorithm();

        // 执行Dijkstra算法
        dijkstra.FindShortestPath(edges, nodes, 1);

        // 输出结果
        foreach (var node in nodes)
        {
            Console.WriteLine($"Node {node.Id}: Shortest distance = {node.Distance}");
        }
    }
}